package org.algorithm.Backtracking.leetcode40;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {

    /**
     * candidates 中有重复元素，并且只能取一次，需要考虑横向重复
     */
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> item = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        boolean[] used = new boolean[candidates.length];
        Arrays.fill(used,false);
        Arrays.sort(candidates);
        backtracking(candidates,target,0,used,0);
        return res;
    }


    private void backtracking(int[] candidates, int target, int sum, boolean[] used, int index) {
        if (sum == target) {
            res.add(new ArrayList<>(item));
            return;
        }

        if (sum>target){
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            if (i > 0 && candidates[i - 1] == candidates[i] && !used[i - 1]) {
                continue;
            }

            sum += candidates[i];
            item.add(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, sum, used, i+1);

            item.remove(item.size() - 1);
            used[i] = false;
            sum -= candidates[i];
        }
    }
}
